public class Main {
    /* https://leetcode-cn.com/problems/letter-tile-possibilities/submissions/
     * 活字印刷
     * for是横向的，DFS是纵向的
     * 标记数组books
     * */
    public void DFS(HashSet<String> set, String tiles, String curTil, boolean[] books) {
        if (curTil.length() != 0) {
            set.add(curTil);
        }
        for (int i = 0; i < tiles.length(); i++) {
            if (books[i]) {
                books[i] = false;
                DFS(set, tiles, curTil + tiles.charAt(i), books);
                //回溯
                books[i] = true;
            }
        }
    }

    public int numTilePossibilities(String tiles) {
        HashSet<String> set = new HashSet<>();
        boolean[] books = new boolean[tiles.length()];
        DFS(set, tiles, "", books);
        return set.size();
    }
}